package com.ankie.algorithm.leetcode416;

import java.util.ArrayList;

/**
 * 416 题：分割等和子集
 *
 * @author :  ankie
 * Create at:  2020/6/28 15:15
 * Copyright: (c)2020 Ankie Cloud Inc. All rights reserved.
 * @version : 1.0
 */
public class PartitionEqualSubsetSum {

    /**
     * 二维版本的dp
     * 题解思路：https://leetcode-cn.com/problems/partition-equal-subset-sum/solution/0-1-bei-bao-wen-ti-xiang-jie-zhen-dui-ben-ti-de-yo/
     *
     */
    public static boolean canPartition2(int[] nums) {
        int len = nums.length;
        if (len == 0) return false;
        int sum = 0;
        for (int num : nums) sum += num;
        // 两个数组和相同，他们再相加的和一定为偶数
        if ((sum % 2) == 1) return false;
        int target = sum / 2;
        // 创建二维状态数组，行：物品索引，列：容量（包括 0）
        boolean[][] dp = new boolean[len][target + 1];
        // 先填表格第 0 行，第 1 个数只能让容积为它自己的背包恰好装满
        if (nums[0] <= target) dp[0][nums[0]] = true;

        // 再填表格后面几行
        for (int i = 1; i < len; i++) {
            for (int j = 0; j <= target; j++) {
                // 直接从上一行先把结果抄下来，然后再修正
                dp[i][j] = dp[i - 1][j];
                if (nums[i] == j) {
                    dp[i][j] = true;
                    continue;
                }
                if (nums[i] < j) {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                }
            }
        }
        return dp[len - 1][target];
    }

    /**
     * 一维版本的 dp
     */
    public static boolean canPartition1(int[] nums) {
        int sum = 0;
        for (int num : nums) sum += num;
        // 和为奇数时，不可能划分成两个和相等的集合，
        // 因为分成两个数组的和相等，即使这两个数组的和分别为奇数，那么原数组的和还是偶数
        if (sum % 2 != 0) return false;
        sum = sum / 2;
        boolean[] dp = new boolean[sum + 1];                    // 构建了一个boolean类型的数组，长度为数组的和，并将数组中除了第一个为true，其余全为false
        for (int i = 0; i < dp.length; i ++) dp[i] = false;
        dp[0] = true;

        for (int i = 0; i < nums.length; i++) {                           // 从数组头开始遍历
            for (int j = sum; j >= 0; j--) {                    // 从总和向下遍历，每次j--，当 j - nums[i]，也就是总和减去真正数组中数据为正的时候，对当前位置的dp赋值
                if (j - nums[i] >= 0) {
                    dp[j] = (dp[j] || dp[j - nums[i]]);
                }
            }
        }
        return dp[sum];
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1, 5, 11, 5};
        int[] arr1 = new int[]{1, 2, 4, 5};
        System.out.println("result: " + canPartition2(arr1));
    }
}

/**
 * ---- 背包问题 ----
 * 给你一个可装载重量为 w 的背包和 n 个物品，每个物品有重量和价值的两个属性。
 * 其中第 i 个物品的重量为 wt[i]，价值为 val[i]，
 * 现在让你用这个背包装物品，最多能装的价值是多少？
 *
 * 那么对于这个问题，我们可以先对集合求和，得出sum，先把问题转化为背包问题
 * 给定一个可装载重量为 sum/2 的背包和 n 个物品，每个物品的重量为 num[i]。
 * 现在让你装物品，是否存在一种装法，能够恰好将背包装满？
 */

/**
 * 第一步：明确两点，【状态】和【选择】
 *      状态就是【背包的容量】和【可选择的物品】，选择就是【装进背包】或者【不装进背包】
 * 第二步：明确 dp 数组的定义
 *      按照背包问题的套路，可以给出如下定义
 *      dp[i][j] = x表示，对于前 i 个物品，当前背包的容量为 j 时，
 *      若 x 为 true，则说明可以恰好将背包装满，
 *      若 x 为 false，则说明不能恰好将备好装满。
 *
 *      比如说，如果 dp[4][9] = true，其含义为：对于容量为 9 的背包，若只是用前 4 个物品，
 *      可以有一种方法把背包恰好装满。
 *
 *      或者说对于本体，含义是对于给定的集合中，若只对前 4 个数字进行选择，
 *      存在一个子集的和可以恰好凑出 9。
 *
 *      根据这个定义，我们相求的最终答案就是 dp[N][sum/2]，
 *      base case 就是 dp[...][0] = true 和 dp[0][...] = false，
 *      因为背包没有空间的时候，就相当于装满了，而当没有物品可以选择的时候，肯定没办法装满背包
 * 第三步：根据【选择】，思考状态转移的逻辑。
 *      回想刚才的 dp 数组的含义，可以根据【选择】对 dp[i][j] 得到以下状态转移：
 *
 *      如果不把 nums[i] 算入子集，或者说你不把这第 i 个物品装入背包，那么是否能够恰好装满背包，
 *      取决于上一个状态 dp[i-1][j]，继承之前的结果。
 *
 *      如果把 nums[i] 算入子集，或者说你把这第 i 个物品装入了背包，那么是否能够恰好装满背包，
 *      取决于状态 dp[i - 1][j-nums[i-1]]
 *
 *      首先，由于 i 是从 1 开始的，而数组索引是从 0 开始的，所以第 i 个物品的重量应该是 nums[i-1]，
 *      这一点不要搞混
 *
 *      dp[i - 1][j-nums[i-1]]也很好理解：你如果装了第 i 个物品，就要看背包的剩余重量
 *      j - nums[i-1] 限制下是否能够恰好被装满
 *
 *      换句话说，j - nums[i-1] 的重量可以恰好被装满，那么只要把第 i 个物品装进去，
 *      也可恰好装满 j 的重量；否则的话，重量 j 肯定是装不满的
 * 第四步：将伪代码翻译成代码，处理一些边界情况。
 */